﻿// 2-4 0-1背包问题 (15分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

// 2-2 矩阵链乘 (20分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
using namespace std;
vector<string>shchu;


void sdeal(string* zifushuz, int a, int b) {//对字符串加括号处理
	//stack<char>c;

	if (a == b)
	{


	}
	else
	{
		zifushuz[a] = "(" + zifushuz[a];
		zifushuz[b] = zifushuz[b] + ")";
	}



}
void digui(int** mat, int i, int j, int* s, int* v,set<int>&number)//这里set的引用差点忘记写
{
	
		if (i == 0 || j == 0)
		{
			;
		}
		else if (j < s[i - 1])
		{
			digui(mat, i - 1, j, s, v,number);
			//mat[i][j] = mat[i - 1][j];
		}
		else if (i > 0 && j >= s[i - 1])
		{
			int x, y;
			x = mat[i - 1][j];
			y = mat[i - 1][j - s[i - 1]] + v[i - 1];
			if (x > y)
			{
				digui(mat, i - 1, j, s, v,number);
			}
			else
			{
				if (1)//x != y
				{
					
					digui(mat, i - 1, j -( s[i - 1]), s, v,number);
					//cout << " " << s[i - 1];
					//cout << number.size();
					number.insert(s[i - 1]);
					
					
				}
				else//相同的情况再考虑吧
				{

				}
			}
		}
}
void com(int** mat, int i, int j, int* s, int* v) 
{

	if (i==0|| j == 0)
	{
		mat[i][j]=0;
	}
	else if (j <s[i-1])
	{
		mat[i][j] = mat[i-1][j];
	}
	else if (i > 0 && j >= s[i - 1])
	{
		int x, y;
		x = mat[i - 1][j];
		y = mat[i - 1][j - s[i - 1]] + v[i - 1];
		if (x > y)
		{
			mat[i][j] = x;
		}
		else
		{
			mat[i][j] = y;
		}
	}
}
int main()
{

	int i, j, C,n;
	set<int>number;//存放那些最后出现的s[i]
	cin >> n>>C;
	//存入每个物品的体积和价值
	int* s = new int[n ];//这个s其实是倒序
	int* right_s = new int[n];
	int* v = new int[n ];
	for (i = 0; i < n ; i++)
	{
		cin >> right_s[i];
	}
	for (i = 0; i < n; i++)
	{
		 s[n-1-i]= right_s[i];
	}
	for (i = n-1; i >=0 ; i--)
	{
		cin >> v[i];
	}

	/*输入矩阵
	int* shuru = new int[n + 1];
	for (i = 0; i < n + 1; i++)
	{
		cin >> shuru[i];
	}
	//初始化字符串数组,如5个矩阵这个就是12345,然而非个位数不会是整体，如((M1(M2(M3(M4(M5M6)))))(((M7M8)M9)M1M0)
	string* zifushuzu = new string[n];
	for (i = 0; i < n; i++)
	{
		zifushuzu[i] = "M" + to_string(i + 1);
	}*/

	//cout << C << endl;
	//建立矩阵
	int** mat = new int* [n+1];

	for (i = 0; i < n+1; i++)
	{
		mat[i] = new int[C+1];
	}
	//初始化第一横纵全为0
	for (i = 0; i < n+1; i++)
	{
		mat[i][0] = 0;
	}
	for (i = 0; i < C + 1; i++)
	{
		mat[0][i] = 0;
	}


	//逐行读矩阵，从【1,1】开始

	for (i = 1; i < n + 1; i++)
	{ 
		
		for (j = 1; j < C+1; j++)
		{
			com(mat, i, j, s,v);//mat[i][jj] = 0;
			
		}
	}
	/*
	for (i = 0; i < n + 1; i++)
	{

		for (j = 0; j < C + 1; j++)
		{
			cout << mat[i][j] << "     ";

		}
		cout <<  "\n";
	}
		*/

	digui(mat,  n ,C, s,v, number);
	cout << mat[n][C]<<" ";
	for (i = 0; i < n ; i++)
	{
		if (number.count(right_s[i]))
		{
			cout << "1";
		}
		else
		{
			cout << "0";
		}
	}



}


